package nextoffer;

class Tree2 {
        public static boolean verifyPostorder(int[] postorder) {

            if(postorder.length==0) return  true;
           return verify(postorder,0,postorder.length-1);

        }

        public static boolean verify (int[] postorder,int l,int r)
        {
            if(l>=r) return true;
            //root
            int rot = postorder[r];
            int right = l; //右子树节点
            int i ;
            for(i = l ; i < r;i++)  //找到右子树
            {
                if(postorder[i]>rot)//如果某个节点大于 跟 那么是右子树开始划分
                {
                    right = i;break;
                }
            }
            int k ;
            for(k = i ; k < r;k++) //看右子树有无比根结点小的
            {
                if(postorder[k]<rot)return  false;
            }
            return verify(postorder,l,right-1)&&verify(postorder,right,r-1);



            }

        public static void main(String[] args) {
            int[] arr = new  int[]{4, 6, 7, 5};
            System.out.println(Tree2.verifyPostorder(arr));
        }



}
